package HashTable;

import java.util.*;

public class _347_TopKFrequentElements {
    public List<Integer> topKFrequent(int[] nums, int k) {
        //get every num's origin count
        Map<Integer, Integer> originMap = new HashMap<>();
        for (int num : nums) {
            originMap.put(num, originMap.getOrDefault(num, 0) + 1);
        }
        //compare
        List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(originMap.entrySet());
        Collections.sort(entryList, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue()-o1.getValue();
            }
        });
        int count = 0;
        List<Integer> res = new ArrayList<>();
        Iterator<Map.Entry<Integer, Integer>> iter = entryList.iterator();
        while (iter.hasNext()) {
            if (count < k) {
                Map.Entry<Integer, Integer> entry = iter.next();
                res.add(entry.getKey());
            } else {
                break;
            }
            count++;
        }
        return res;
    }
}
